package com.pisolution.scheduler.core.graph;

import org.apache.commons.collections.CollectionUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 有向无环图.
 *
 * @param <Node> 图节点标识类型.
 * @param <NodeInfo> 图节点中存储的数据类型.
 * @param <EdgeInfo> 图中边的类型.
 *
 * @author sora
 * @version 0.1.0
 */
public final class Graph<Node, NodeInfo, EdgeInfo> {
    private static final Logger LOGGER = LoggerFactory.getLogger(Graph.class);

    // -------------------------------------------------------------------------------------------------

    /** 用于存储图的节点信息. */
    private final Map<Node, NodeInfo> nodes;

    /** 用于存储图中边的信息 存储方式为: 源节点 -> [目标节点, 边数据]. */
    private final Map<Node, Map<Node, EdgeInfo>> edges;

    /** 用于以逆向的方式存储图中边的信息 存储方式为: 目标节点 -> [源节点, 边数据]. */
    private final Map<Node, Map<Node, EdgeInfo>> reverseEdges;

    // -------------------------------------------------------------------------------------------------

    /** 用于阻止并发访问修改图. */
    private final ReadWriteLock lock;

    // -------------------------------------------------------------------------------------------------
    //  初始化
    // -------------------------------------------------------------------------------------------------

    /**
     * 初始化图.
     */
    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashMap<>();
        this.reverseEdges = new HashMap<>();

        this.lock = new ReentrantReadWriteLock();
    }

    // -------------------------------------------------------------------------------------------------
    //  构建图
    // -------------------------------------------------------------------------------------------------

    /**
     * 添加图的节点.
     *
     * @param node 节点标识.
     * @param info 节点数据.
     */
    public void addNode(@Nonnull final Node node, @Nullable final NodeInfo info) {
        // 1. 限制图访问.
        this.lock.writeLock().lock();

        try {
            this.nodes.putIfAbsent(node, info);
        } finally {
            // 2. 取消限制.
            this.lock.writeLock().unlock();
        }
    }

    /**
     * 添加图的边.
     *
     * @param from 起始节点.
     * @param to 终止节点.
     */
    public void addEdge(@Nonnull final Node from, @Nonnull final Node to) {
        // 1. 限制图访问.
        this.lock.writeLock().lock();

        try {
            // 2. 检测如果添加这条边是否会引起回环.
            if (this.hasCycleIfAddEdge(from, to)) {
                LOGGER.error("The graph will be in cycle if the edge {} -> {} added to the graph.", from, to);

                return;
            }

            // 3. 添加边至图中.
            this.edges.putIfAbsent(from, new HashMap<>());
            this.edges.get(from).putIfAbsent(to, null);

            // 4. 添加逆向边至临时性存储介质中.
            this.reverseEdges.putIfAbsent(to, new HashMap<>());
            this.reverseEdges.get(to).putIfAbsent(from, null);
        } finally {
            // 5. 取消限制.
            this.lock.writeLock().unlock();
        }
    }

    /**
     * 检测如果添加给定边是否会引起图中出现回环链路.
     *
     * @param from 起始节点.
     * @param to 终止节点.
     *
     * @return 如果会引起回环则返回 {@code true} 否则返回 {@code false}.
     */
    private boolean hasCycleIfAddEdge(@Nonnull final Node from, @Nonnull final Node to) {
        // 1. 如果起始节点和终止节点是同一个节点则必定出现回环.
        if (from.equals(to)) {
            LOGGER.error("Could not add edge on the same node.");

            return true;
        }

        // 2. 如果起始节点或终止节点缺失 则无法添加边.
        if (!this.nodes.containsKey(from) || !this.nodes.containsKey(to)) {
            LOGGER.error("One of the target nodes is missing.");

            return true;
        }

        // 3. 创建一个临时性队列用于存储子节点信息.
        final Queue<Node> queue = new LinkedList<>();

        // 4. 将终止节点追加到队列中.
        queue.add(to);

        // 5. 以递推的方式寻找终止节点的子节点 如果其子节点中存在起始节点 则确定添加边会引起回环.
        while (!queue.isEmpty()) {
            final Node node = queue.poll();

            for (final Node subsequentNode: this.getSubsequentNodes(node)) {
                if (subsequentNode.equals(from)) {
                    return true;
                }

                queue.add(subsequentNode);
            }
        }

        return false;
    }

    // -------------------------------------------------------------------------------------------------
    //  访问图
    // -------------------------------------------------------------------------------------------------

    /**
     * 以差集的方式计算获取图的起始节点.
     *
     * @return 图的起始节点集合.
     */
    @SuppressWarnings("unchecked")
    public Collection<Node> getStartNode() {
        // 1. 限制图修改.
        this.lock.readLock().lock();

        try {
            return CollectionUtils.subtract(this.nodes.keySet(), this.reverseEdges.keySet());
        } finally {
            // 2. 取消限制.
            this.lock.readLock().unlock();
        }
    }

    /**
     * 通过节点标识访问节点中存储的数据.
     *
     * @param node 节点标识.
     *
     * @return 该节点中存储的数据.
     */
    public NodeInfo getNode(@Nonnull final Node node) {
        // 1. 限制图修改.
        this.lock.readLock().lock();

        try {
            return this.nodes.get(node);
        } finally {
            // 2. 取消限制.
            this.lock.readLock().unlock();
        }
    }

    /**
     * 获取给定节点的子节点.
     *
     * @param node 节点标识.
     *
     * @return 该节点的子节点集合.
     */
    public Set<Node> getSubsequentNodes(@Nonnull final Node node) {
        // 1. 限制图修改.
        this.lock.readLock().lock();

        try {
            return this.edges.getOrDefault(node, Collections.emptyMap()).keySet();
        } finally {
            // 2. 取消限制.
            this.lock.readLock().unlock();
        }
    }
}
